\section{石子合并(P1880)}

\subsection{题目描述}

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，
并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

\subsection{输入}
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

\subsection{输出}
输出共2行,第1行为最小得分,第2行为最大得分.

\subsection{样例}
\subsubsection{输入样例\#1}
\begin{lstlisting}
4
4 5 9 4
\end{lstlisting}
\subsubsection{输入样例\#1}
\begin{lstlisting}
43
54
\end{lstlisting}

\subsection{分析}
首先，读题时需要注意: “圆形操场”，也就是按照圆形堆放，首尾相连。

N堆石子合并成一堆，每次合并都有得分产生，最后的得分是所有中间得分的总和。

如果用深搜来做，定义个函数： dfs(s, e, rmin, rmax)，用来计算把[s, j]和[j+1, e]两个
区间合并之后的得分，如此逐层向下搜索，理论上复杂度是$O(n^2)$，但是因为是圆形排列，所以
复杂度变成了$O(n^3)$，有因为是递归，所以开销会大很多，所以深搜无法在规定时间内得到结果。

改为DP来做，定义$f_max[s][e]$为合并从s到e的最大总得分（包含这两个这两次合并之前所有其
他合并的得分）。那么状态转换表达式为：
\[
   f\_max[s][e] = max(f\_max[s][e], f\_max[s][j]+f\_max[j+1][e]+sum[s][e]) 
\]
其中$sum[s][e]$为第s堆石子到第e堆石子的总和。其意义是把第s到j堆合并总得分$f\_max[s][j]$
和$j+1$到e堆的合并总得分$f\_max[j+1][e]$加起来，挑选出其中最大的一个总得分之和，再加上最后
这次合并的得分$sum[s][e]$，就是s到e的最大总得分。

状态转换表达式的关键点是：正确理解总得分的计算规则，这个规则是：所有之前的得分加上本次合并的得分。

同理$f\_min[s][e]$为s到e的最小得分，以上状态转换关系中的max改为min。

\subsubsection{所用技巧}
\begin{compactitem}
\item 环形排列，把原来的n堆石子扩大一倍，变成2n堆，然后循环查找从$f\_max[i][i+n-1], i=[1..n]$范围内的最大值。
\item 计算$sum[i][j]$，可以先计算一维数组，$sum1d[i] = sum(a[1], ..., a[i])$，然后$sum[i][j]=sum1d[j] - sum1d[i-1]$，
      这样可以避免两个循环来计算$sum[i][j]$。
\end{compactitem}

\subsubsection {相似经典问题}
我暂时没想出来。

\subsubsection {相关基础知识}
无，似乎不需要很特别的知识。

\subsubsection {所用方法}
\begin{compactitem}
\item DP，动态规划。
\end{compactitem}

\subsection{代码}
\begin{lstlisting}
#include <cstdio>
#include <algorithm>

#define INF 999999999
 
#define N 220

using namespace std; 

int a[N]; 
int n; 

int sum[N]; 
int f_max[N][N]; 
int f_min[N][N]; 

void solve(int &rmin, int &rmax)
{
	int i, j; 
	int s, e, t; 
	int n2 = 2*n; 
	
	for (i=1; i<n2; i++) {
		for (s=1; s+i<=n2; s++) {
			e = s+i; 
			f_min[s][e] = INF; 
			for (j=0; j<i; j++) {
				t = f_max[s][s+j]+f_max[s+j+1][e];  
				f_max[s][e] = max(f_max[s][e], t); 
				f_min[s][e] = min(f_min[s][e], t); 
			}
			// skill 1: calculate range sum, 
			// don't use a 2d array
			t = sum[e] - sum[s-1]; 
			f_max[s][e] += t; 
			f_min[s][e] += t; 
		}
	}
	rmin = INF; 
	rmax = 0; 
	for (i=1; i<=n; i++) {
		rmin = min(rmin, f_min[i][i+n-1]); 
		rmax = max(rmax, f_max[i][i+n-1]); 
	}
}


int main()
{
	int i; 
	int rmax, rmin; 	
	
	scanf("%d", &n); 
	for (i=1; i<=n; i++) {
		scanf("%d", &a[i]); 
		a[n+i] = a[i]; 
		//skill 2: to deal with circlar permutaiton
		sum[i] = sum[i-1] + a[i]; 	
	}

	for (i=n+1; i<=2*n; i++) {
		sum[i] = sum[i-1] + a[i]; 
	}

	solve(rmin, rmax); 
	
	printf("%d\n%d\n", rmin, rmax); 

	return 0; 
}


\end{lstlisting}


